#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int k = m * n;

        int l = 0, r = k - 1;

        while (l <= r) {
            int mid = (l + r) >> 1;

            int mid_r = mid / n;
            int mid_c = mid % n;

            if (matrix[mid_r][mid_c] == target) {
                return true;
            }

            if (matrix[mid_r][mid_c] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        return false;
    }
};

int main() {
    int target = 3;
    vector<vector<int>> nums = {{1,3,5,7},{10,11,16,20},{23,30,34,60}};

    cout << Solution().searchMatrix(nums, target) << endl;

    return 0;
};